#pragma once
#include <vector>
#include <iostream>
using namespace std;
template<typename Comparable>
class BinarySerach
{
public:
	BinarySerach();
	~BinarySerach();


	int find(const std::vector<Comparable> & vec,const  Comparable & ob);


	//call oriBinarySearch
	int oriBinSearch(const std::vector<Comparable> & vec, const  Comparable & ob);

	//rank: return the postion which the object should take instead of returning -1 when it doesn;t exit
	//call rannkBinarySearch
	int rank(const std::vector<Comparable> & vec, const  Comparable & ob);

	// refinement of previous version
	int refinedRank(const std::vector<Comparable> & vec, const  Comparable & ob);

	int noRecursiveRank(const std::vector<Comparable> & vec, const  Comparable & ob);
private:
	
	int rannkBinarySearch2(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi);
	int rannkBinarySearch(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi);
	int oriBinarySearch(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi);
	int noRecursiveRank(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi);
};


template<typename Comparable>
BinarySerach<Comparable>::BinarySerach()
{
}

template<typename Comparable>
BinarySerach<Comparable>::~BinarySerach()
{
}


template<typename Comparable>
int BinarySerach<Comparable>::find(const std::vector<Comparable> & vec, const Comparable & key)
{


}


template<typename Comparable>
int BinarySerach<Comparable>::oriBinSearch(const std::vector<Comparable> & vec, const  Comparable & ob)
{
	
	//return vec.size();
	return oriBinarySearch(vec, ob, 0, vec.size() - 1);
}



template<typename Comparable>
int BinarySerach<Comparable>::oriBinarySearch(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi)
{
	if (low > hi)
		return -1;
	int mid = low + (hi - low) / 2;
	if (ob < vec[mid])
		return rannkBinarySearch2(vec, ob, low, mid - 1);
	else if (ob > vec[mid])
		return rannkBinarySearch2(vec, ob, mid + 1, hi);
	else
	{
		return mid;
	}
}


template<typename Comparable>
int BinarySerach<Comparable>::rank(const std::vector<Comparable> & vec, const  Comparable & ob)
{
	return rannkBinarySearch(vec, ob, 0, vec.size());
}


template<typename Comparable>
int BinarySerach<Comparable>::rannkBinarySearch(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi)
{
	cout << "I have been abandoned" << endl;
	return -999;
}



template<typename Comparable>
int BinarySerach<Comparable>::refinedRank(const std::vector<Comparable> & vec, const  Comparable & ob)
{
	return rannkBinarySearch2(vec, ob, 0, vec.size() - 1);
}

template<typename Comparable>
int BinarySerach<Comparable>::rannkBinarySearch2(const std::vector<Comparable> & vec, const  Comparable & ob, int low, int hi)
{
	if (low > hi)
		return low;
	int mid = low + (hi - low) / 2;
	if (ob < vec[mid])
		return rannkBinarySearch2(vec, ob, low, mid - 1);
	else if (ob > vec[mid])
		return rannkBinarySearch2(vec, ob, mid + 1, hi);
	else
	{
		return mid;
	}
}

template<typename Comparable>
int BinarySerach<Comparable>::noRecursiveRank(const std::vector<Comparable> & vec, const  Comparable & ob)
{
	return noRecursiveRank(vec, ob, 0, vec.size() - 1);
}


template<typename Comparable>
int BinarySerach<Comparable>::noRecursiveRank(const std::vector<Comparable> & vec, const  Comparable & ob,int low , int hi)
{
	int mid = 0;
	while (low <= hi)
	{
		mid = low + (hi - low) / 2;
		if (ob > vec[mid])
			low = mid + 1;
		else if (ob < vec[mid])
			hi = mid - 1;
		else
		{
			return mid;
		}


	}
	return low;
}